package Other;

/**
 * Created by Lee on 2017/3/6 0006.
 */
public class FourSplit {

//    对于一个长度为N的整型数组A， 数组里所有的数都是正整数，对于两个满足0<=X <= Y <N的整数，A[X], A[X+1] … A[Y]构成A的一个切片，记作(X, Y)。
//    用三个下标 m1, m2, m3下标满足条件 0 < m1, m1 + 1 < m2, m2 +1 < m3 < N – 1。
//    可以把这个整型数组分成(0, m1-1), (m1+1, m2-1), (m2+1, m3-1), (m3+1, N-1) 四个切片。如果这四个切片中的整数求和相等，称作“四等分”。
//    编写一个函数，求一个给定的整型数组是否可以四等分，如果可以，返回一个布尔类型的true，如果不可以返回一个布尔类型的false。
//    限制条件： 数组A最多有1,000,000项，数组中的整数取值范围介于-1,000,000到1,000,000之间。
//    要求： 函数的计算复杂度为O(N)，使用的额外存储空间（除了输入的数组之外）最多为O(N)。
//    例子：
//    对于数组A=[2, 5, 1, 1, 1, 1, 4, 1, 7, 3, 7] 存在下标 2, 7, 9使得数组分成四个分片[2, 5], [1, 1, 1, 4], [7], [7]，这三个分片内整数之和相等，所以对于这个数组，函数应该返回true。
//    对于数组 A=[10, 2, 11, 13, 1, 1, 1, 1, 1]， 找不到能把数组四等分的下标，所以函数应该返回false。

    public static void main(String[] args) {
//        int[] A={1,1,1,1,7,1,3,4,1,2,1,5,2,2};
//        int[] A={1,1,1,1,10,1,3,1,1,2,1,5,2,2};
//        int[] A={1,1,1,4,3,3,3,4,1,1,1};
//        int[] A={2,5,1,1,1,1,4,3,7,5,7};
//        int[] A={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
//        int[] A={1,1,1};

        int[] A={1,1,1,1,1,1,1};
        Boolean res = solution2(A);
        System.out.println(String.valueOf(res));
    }

    public static boolean solution2(int[] A) {
        int length=A.length;
        if (length<7)
            return false;
        int i=0,j=length-1;
        int sum=0;
        while(i<=j){
            //查找第一和第二个分割点 既v1 v3
            int[] re = findV1andV3(A, i, j, sum);
            //如果没有找到。则返回false
            if(re==null){
                break;
            }
            //否则保存当前查找到的 v1 v3 以及 sum1
            i=re[1];
            j=re[3];
            sum=re[0];
            System.out.println("v1="+i+",v3="+j);
//        int[] re = findValLocate(A);
            //通过sum1  查找（v1,v3)  范围内的 v2的位置
            re[2] = findV2orV3(A, re[0], re[1] + 1, re[3] - 1);
            if(re[2]==-1){
                continue;
            }
            //根据sum1  查找(v2,v3]范围类的v3点，若新找出的v3 与 原v3相等，则返回true
            int v3 = findV2orV3(A, re[0], re[2] + 1, re[3]);
            if (v3 == re[3]) {
                System.out.println("v2="+re[2]+",sum="+sum);
                return true;
            }
        }
        return false;

    }


    /*
    * 查找下一个分割点，主要用于查找第2个分割点
    * 再用此函数查找第三个分割点与原来找出的分割点作比较，如果一致则正确
    *
    * */
    public static int findV2orV3(int[] A, int val, int begin, int end) {
        int s=0;
        for(int i=begin;i<end;++i) {
            s += A[i];
            if (s == val) {
                return i+1;
            }
        }
        return -1;
    }


    /*
    * 查找 第1和第3个分割点
    * i从上次查找到的位置开始递增，j从上次查到的第3个分割点开始递减
    *lo为上次查找到的分割点的位置-1
    * high为分割点的位置+1
    * sTemp为0到i的sum
    * */
    public static int[] findV1andV3(int[] A,int lo,int high,int sTemp) {
        int s1=sTemp+A[lo],s4=sTemp+A[high];
        for(int i=lo+1,j=high-1;i<j;) {
            if (s1 < s4) {
                s1 += A[i];
                i++;
            }else if(s1>s4){
                s4 += A[j];
                j--;
            }else{
                int m=(A.length)-3-(i+A.length-j-1);
                if(m>=2&&m<=2*s1){
                    int[] re = {s1, i, 0, j};
                    return re;
                }else{
                    s1 += A[i];
                    s4 += A[j];
                    j--;
                    i++;
                }
            }
        }
        return null;
    }
}
